0% completed
Problem Statement
Given an array nums containing integers in non-decreasing order and integer target, return the index if the target is found. If not, return the index where it can be placed such that the final array elements are in non-decreasing order.
You must solve the problem in
Examples
-
Example 1:
- Input: nums = [2,4,6,8,10], target = 1
- Expected Output: 0
- Justification: The target number 1 does not exist in the array but should be inserted at index 0 to keep the array in ascending order.
-
Example 2:
- Input: nums = [1,3,7,9,11], target = 10
- Expected Output: 4
- Justification: The target number 10 is not present in the array. It fits between 9 and 11, making the fourth index (0-based indexing) its rightful position.
-
Example 3:
- Input: nums = [5,8,12], target = 12
- Expected Output: 2
- Justification: The number 12 is present at index 2 in the array.
Solution
To solve this problem, we will employ a binary search approach due to its
Initially, we define two pointers representing the search interval's bounds: left at the start and right at the end of the array. In each iteration, we compare the target with the middle element of the search interval. If the target is less than the middle element, we move the right pointer to the middle, narrowing our search to the lower half. If the target is greater, we adjust the left pointer to just past the middle element, shifting our focus to the upper half. This process continues until left meets right, indicating the target's position or insertion point, thereby ensuring that our approach is both efficient and effective.
Step-by-Step Algorithm
-
Initialize Pointers: Start by initializing two pointers,
leftandright, to point at the start and end of the array, respectively.leftis set to 0, andrightis set to the length of the array minus one. -
Binary Search Loop: While the
leftpointer is less than or equal to therightpointer, perform the following steps to narrow down the search for the target or its insertion position:- Calculate the middle index,
mid, as the average ofleftandright((left + right) / 2). To avoid potential overflow, you can useleft + (right - left) / 2. - Compare the target value with the element at the middle index (
nums[mid]).- If
nums[mid]is equal to the target, then the target is found. Return themidindex as the position where the target exists within the array. - If
nums[mid]is less than the target, it means the target, if it exists, must be in the right half of the current segment. Updatelefttomid + 1to narrow the search to the right half. - If
nums[mid]is greater than the target, this indicates that the target, if present, is in the left half. Updaterighttomid - 1to focus the search on the left half.
- If
- Calculate the middle index,
-
Identify Insert Position: If the loop terminates without finding the target (i.e.,
left>right), it means the target does not exist in the array and should be inserted. At this point,leftpoints to the index where the target should be inserted to maintain the sorted order of the array. Returnleftas the insertion index.
Algorithm Walkthrough
Let's consider the input: nums = [2,4,6,8,10], target = 1.
-
Step 1: Initialize
left = 0andright = 4(since the array has 5 elements, and indices start at 0). -
Step 2: Enter the binary search loop:
- First Iteration:
- Calculate
mid = (0 + 4) / 2 = 2.nums[2]is 6. - Since 6 is greater than 1, update
righttomid - 1 = 1.
- Calculate
- Second Iteration:
leftis still 0, andrightis now 1. Calculatemid = (0 + 1) / 2 = 0(integer division).nums[0]is 2, which is greater than 1. So, updaterighttomid - 1 = -1.
- Third Iteration:
- Now, both
left>right. So, the loop terminates.
- Now, both
- First Iteration:
-
Step 3: Since the loop has terminated and we did not find the target value of 5,
leftis at the position where 5 should be inserted to maintain the array's order. In this case,leftis 0, indicating that the target number 5 should be inserted at index 2.
Code
Complexity Analysis
Time Complexity:
- The algorithm uses binary search to find the target's position or the insertion point in the array. Since binary search divides the search interval in half at each step, the time complexity is logarithmic.
- With each comparison, it either finds the target or halves the search range, leading to a maximum of
comparisons, where n is the number of elements in the array.
Space Complexity:
The algorithm uses a fixed amount of extra space for variables, regardless of the input size. Therefore, the space complexity is constant, as it does not require additional space that scales with the input size.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity:
Space Complexity: